package com.cn.algorithm.one.list;

public class CircleDequeue<E> {

    public static final int DEFAULT_CAPACITY = 10;

    int size;

    int front;

    E[] elements;

    public CircleDequeue(int capacity) {
        if (capacity < DEFAULT_CAPACITY) {
            capacity = DEFAULT_CAPACITY;
        }
        this.elements = (E[]) new Object[capacity];
    }

    public CircleDequeue() {
        this(DEFAULT_CAPACITY);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[index(i)] = null;
        }
        size = 0;
        front = 0;
    }

    public E front() {
        return elements[front];
    }

    public E tail() {
        return elements[index(size - 1)];
    }

    public void leftPush(E element) {
        checkCapacity(size + 1);
        front = index(-1);
        elements[front] = element;
        size++;
    }

    public void rightPush(E element) {
        checkCapacity(size + 1);
        elements[index(size++)] = element;
    }

    public E leftPop() {
        E oldElement = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return oldElement;
    }

    public E rightPop() {
        int lastIndex = --size;
        E oldElement = elements[lastIndex];
        elements[lastIndex] = null;
        return oldElement;
    }

    public int index(int index) {
        index += front;
        if (index < 0) {
            return index += elements.length;
        }
        return index >= elements.length ? (index - elements.length) : index;
    }

    public void checkCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (capacity <= oldCapacity) {
            return;
        }
        E[] oldElements = elements;
        elements = (E[]) new Object[oldCapacity + (oldCapacity >> 1)];
        for (int i = 0; i < oldElements.length; i++) {
            elements[i] = oldElements[i];
        }
        front = 0;
    }

    public static void main(String[] args) {
        CircleDequeue<Integer> circleQueue = new CircleDequeue<>();
        for (int i = 0; i < 50; i++) {
            circleQueue.rightPush(i);
        }
        System.out.println(circleQueue.size());
        for (int i = 0; i < 40; i++) {
            System.out.println(circleQueue.leftPop());
        }
        System.out.println(circleQueue.size());
    }
}
